function lowbit(n) {
  return n & -n
}
//树状数组  https://blog.csdn.net/qq_40941722/article/details/104406126
/*
用于解决频繁更新数组的值，并输出前缀和的情况
*/
class FenwickTree {
  constructor(nums) {
    this.nums = nums
    this.n = nums.length
    this.c = null
    this.genTree()
  }
  update(idx, val) {
    this.checkIdx(idx)
    while (idx < this.n) {
      this.c[idx] += val
      idx += lowbit(idx)
    }
  }
  getSum(idx) {
    this.checkIdx(idx)
    let res = this.c[0]
    while (idx > 0) {
      res += this.c[idx]
      idx -= lowbit(idx)
    }
    return res
  }
  genTree() {
    this.c = Array(this.n).fill(0)
    this.c[0] = this.nums[0]
    for (let i = 1; i < this.n; i++) {
      this.update(i, this.nums[i])
    }
  }
  refreshTree(nums) {
    this.nums = nums
    this.n = nums.length
    this.genTree()
  }
  checkIdx(idx) {
    if (idx >= this.n || idx < 0) {
      throw Error('错误的参数')
    }
  }
}

// let nums = [1, 4, 3, 5, 6, 2, 9, 8, 7]
// nums = Array(6).fill(0)
// let tree = new FenwickTree(nums)
// for (let i = 0; i < nums.length; i++) {
//   console.log(tree.getSum(i))
// }
// console.log('arr: ', tree.c)
// console.log('nums: ', nums)

export { FenwickTree }
